ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group95c.txt/000054_icon-group-sender _Mon Oct 16 12:02:00 1995.msg

Internet Message Format | 1996-01-03 | 4KB

Received: by cheltenham.cs.arizona.edu; Mon, 16 Oct 1995 10:07:31 MST
Message-Id: <[e-mail]>
Mime-Version: 1.0
Content-Length: 3010
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Date: Mon, 16 Oct 95 12:02 CDT
From: [e-mail]
Subject: Looking for a carton-packing algorithm
To: [e-mail]
Cc: [e-mail]
X-Mailer: SPRY Mail Version: 04.00.06.17
Errors-To: [e-mail]

>Sorry this is not a specifically Icon issue, but i know Icon
people are interested in this kind or "real-world" problem, so
maybe someone here can at least give me pointers.

As it turns out, Icon is probably at least conceptually the IDEAL language for
precisely this problem. I can't imagine any other language better suited.

>I'm writing a warehouse-management program, and part of the
shipping side of it is assigning the right size carton to ship an
order. We have the carton sizes, and the sizes of the several
items. How to find a carton that will fit the items we want to
ship?

Or several smaller cartons, perhaps of various sizes.

I actually worked on developing a fully automated/robotized PC-based
pick/pack/ship system almost ten years ago in France, (the ultimate customer of
the system, as it turns out, was IBM France) where we had this exact same
problem (and solved it, but it was my colleagues in the company I was working
with who worked on this part of the problem).

It's actually an EXTREMELY interesting problem, for several reasons including
the following:

1)  Shipping cost is a function of the number, sizes and weights of individual
packages, but cartons bigger than a certain size or weight cannot be shipped at
all by some carriers (and it's probably a good idea to ship all the cartons of a
given shipment together by the same carrier, when possible);

2)  The items that go into each carton should (ideally) come as close as
possible to filling each carton (this is the most obvious criteria);

3)  Some items that are being packed may have distinct orientations to be
respected during shipment (This Side Up, etc.)

4)  Fragile or delicate or irregulary-shaped items should generally not be
packed underneath heavy or boxed items.

5)  The resulting fully-packed carton should have a center of gravity which is
as low as possible in the carton, and centered in the carton.  Otherwise, the
sealed carton will be unstable and have an increased tendency to tip over.

6)  As the carton is being packed, the contents need to be at least reasonably
stable in all the intermediate conditions as each new item is added to the ones
already in the carton.  Otherwise, as the robot leaves the carton to fetch the
next item to be packed in it, the stuff shifts and the new item can no longer be
placed where it belongs.

The solution that the company I worked at implemented was done in C, and might
or might not be adaptable to your situation.  If you're interested in contacting
them, the company is "I.R.C.I." and is located in Villejuif, a suburb south of
Paris.  You should be able to get their phone and fax numbers from international
directory assistance, or through the French Minitel directory assistance which
is available through the Net.  IRCI may be willing to license that portion of
their software to your company.  Ask for Philippe Auphelle there (he speaks
perfect English, by the way).

Gordon Peterson
http://www.computek.net/public/gep2/